Search

For more than two decades, proving or refuting the following statement has remained a challenging open problem in the theory of secret sharing schemes (SSSs): every ideal access structure admits an ideal perfect multi-linear SSS. The class of group-characterizable (GC) SSSs include the multi-linear ones. Hence, if the above statement is true, then so is the following weaker statement: every ideal access structure admits an ideal perfect GC SSS. One contribution of this paper is to show that ideal SSSs are not necessarily GC. Our second contribution is to study the above two statements with respect to several variations of weakly-ideal access structures. Recently, Mejia and Montoya studied ideal access structures that admit ideal multi-linear schemes and provided a classification-like theorem for them. We additionally present some tools that are useful to extend their result.

The Langberg-Medard multiple unicast conjecture claims that for any strongly reachable \begin{document}$ k $\end{document} -pair network, there exists a multi-flow with rate \begin{document}$ (1,1,\dots,1) $\end{document} . In this paper, we examine an optimization problem \begin{document}$ \mathcal P_{\mathcal S_k} $\end{document} such that its optimal value \begin{document}$ \mathcal O_{\mathcal S_k} $\end{document} naturally gives a lower bound on the multi-flow rate for the strongly reachable \begin{document}$ k $\end{document} -pair network. We first prove \begin{document}$ \lim_{k\rightarrow \infty}\mathcal O_{\mathcal S_k} = \frac{9}{8} $\end{document} and then show that the multi-flow \begin{document}$ \mathcal C^*_k $\end{document} constructed in our previous work is asymptotically optimal for \begin{document}$ \mathcal P_{\mathcal S_k} $\end{document} and optimal if and only if \begin{document}$ k = 1, 2, 6, 10 $\end{document} .

Graph states are present in quantum information and found applications ranging from quantum network protocols (like secret sharing) to measurement based quantum computing. In this paper, we extend the notion of graph states, which can be regarded as pure quantum graph states, or as homogeneous quadratic Boolean functions associated to simple undirected graphs, to quantum states based on mixed graphs (graphs which allow both directed and undirected edges), obtaining mixed quantum states, which are defined by matrices associated to the measurement of homogeneous quadratic Boolean functions in some (ancillary) variables. In our main result, we describe the extended graph state as the sum of terms of a commutative subgroup of the stabilizer group of the corresponding mixed graph with the edges' directions reversed.

In this paper, a new class of generalized cyclotomic binary sequences with period \begin{document}$ 4p^n $\end{document} is proposed. These sequences are almost balanced, and the explicit formulas of their linear complexity and autocorrelation are presented.

MDS matrices play an important role in the design of block ciphers, and constructing MDS matrices with fewer xor gates is of significant interest for lightweight ciphers. For this topic, Duval and Leurent proposed an approach to construct MDS matrices by using three linear operations in ToSC 2018. Taking words as elements, they found \begin{document}$ 16\times16 $\end{document} and \begin{document}$ 32\times 32 $\end{document} MDS matrices over \begin{document}$ \mathbb{F}_2 $\end{document} with only \begin{document}$ 35 $\end{document} xor gates and \begin{document}$ 67 $\end{document} xor gates respectively, which are also the best known implementations up to now. Based on the same observation as their work, we consider three linear operations as three kinds of elementary linear operations of matrices, and obtain more MDS matrices with \begin{document}$ 35 $\end{document} and \begin{document}$ 67 $\end{document} xor gates. In addition, some \begin{document}$ 16\times16 $\end{document} or \begin{document}$ 32\times32 $\end{document} involutory MDS matrices with only \begin{document}$ 36 $\end{document} or \begin{document}$ 72 $\end{document} xor gates over \begin{document}$ \mathbb{F}_2 $\end{document} are also proposed, which are better than previous results. Moreover, our method can be extended to general linear groups, and we prove that the lower bound of the sequential xor count based on words for \begin{document}$ 4 \times 4 $\end{document} MDS matrix over general linear groups is \begin{document}$ 8n+2 $\end{document} .

In 1943, Hadwiger conjectured that every graph with no K t + 1 minor is t-colorable for every t ≥ 0 . While Hadwiger's conjecture does not hold for list-coloring, the linear weakening is conjectured to be true. In the 1980 s, Kostochka and Thomason independently proved that every graph with no K t minor has average degree O ( t log ⁡ t ) and thus is O ( t log ⁡ t ) -list-colorable. Recently, the authors and Song proved that every graph with no K t minor is O ( t ( log ⁡ t ) β ) -colorable for every β > 1 4 . Here, we build on that result to show that every graph with no K t minor is O ( t ( log ⁡ t ) β ) -list-colorable for every β > 1 4 . Our main new tool is an upper bound on the number of vertices in highly connected K t -minor-free graphs: We prove that for every β > 1 4 , every Ω ( t ( log ⁡ t ) β ) -connected graph with no K t minor has O ( t ( log ⁡ t ) 7 / 4 ) vertices.

Recently, Ivanov et al. proposed a new approach to construct code-based cryptosystems, namely the \begin{document}$ {\sf IKKR} $\end{document} public-key encryptions (PKE) in the International Workshop on Code-Based Cryptography (CBCrypto 2020) [ 9 ]. Unlike the usual construction in code-based encryption schemes which has restrictions on the Hamming weight of the error introduced into the ciphertext, the \begin{document}$ {\sf IKKR} $\end{document} approach allows error vectors of arbitrary weight being introduced into the ciphertext. Using this new approach, Ivanov et al. constructed two cryptosystems, namely the modified and the upgraded \begin{document}$ {\sf IKKR} $\end{document} -PKE. This paper aims to discuss the practical security of the \begin{document}$ {\sf IKKR} $\end{document} -PKE. In particular, we describe the weaknesses in the design of the public key used in the \begin{document}$ {\sf IKKR} $\end{document} -PKE. We exploit such weaknesses and propose two attacks to recover the plaintext in the \begin{document}$ {\sf IKKR} $\end{document} -PKE. The approach of our first attack is similar to the LCKN attack [ 12 ], whilst our second attack is more efficient than the LCKN attack. Our experimental results show that we can recover the plaintext from a given ciphertext in less than 176 milliseconds for schemes based on random Goppa codes and BCH codes.

We use known characterizations of generalized Paley graphs which are cartesian decomposable to explicitly compute the spectra of the corresponding associated irreducible cyclic codes. As applications, we give reduction formulas for the number of rational points in Artin-Schreier curves defined over extension fields and to the computation of Gaussian periods., 20 pages, 2 tables. Added information on Cartesian products of graphs. A general reviwe was made, with small additions improving readability. Some typos corrected. arXiv admin note: text overlap with arXiv:1908.08097

The suffix array, perhaps the most important data structure in modern string processing, is often augmented with the longest common prefix (LCP) array which stores the lengths of the LCPs for lexicographically adjacent suffixes of a string. Together the two arrays are roughly equivalent to the suffix tree with the LCP array representing the tree shape. In order to better understand the combinatorics of LCP arrays, we consider the problem of inferring a string from an LCP array, i.e., determining whether a given array of integers is a valid LCP array, and if it is, reconstructing some string or all strings with that LCP array. There are recent studies of inferring a string from a suffix tree shape but using significantly more information (in the form of suffix links) than is available in the LCP array. We provide two main results. (1) We describe two algorithms for inferring strings from an LCP array when we allow a generalized form of LCP array defined for a multiset of cyclic strings: a linear time algorithm for binary alphabet and a general algorithm with polynomial time complexity for a constant alphabet size. (2) We prove that determining whether a given integer array is a valid LCP array is NP-complete when we require more restricted forms of LCP array defined for a single cyclic or non-cyclic string or a multiset of non-cyclic strings. The result holds whether or not the alphabet is restricted to be binary. In combination, the two results show that the generalized form of LCP array for a multiset of cyclic strings is fundamentally different from the other more restricted forms.

In this paper, we propose a new class of optimal one-coincidence FHS (OC-FHS) sets with respect to the Peng-Fan bounds, including prime sequence sets and HMC sequence sets as special cases. Thereafter, through investigating their properties, we determine all of the FHS distances in the OC-FHS set. Finally, for a given positive integer, we also propose a new class of wide-gap one-coincidence FHS (WG-OC-FHS) sets where the FHS gap is larger than the given positive integer. Moreover, such a WG-OC-FHS set is optimal with respect to the WG-Lempel-Greenberger bound and the WG-Peng-Fan bounds simultaneously.

Subfield codes of linear codes over finite fields have recently received a lot of attention, as some of these codes are optimal and have applications in secrete sharing, authentication codes and association schemes. In this paper, a class of binary subfield codes is constructed from a special family of MDS codes, and their parameters are explicitly determined. The parameters of their dual codes are also studied. Some of the codes presented in this paper are optimal or almost optimal.

A tweakable enciphering scheme (TES) is a length preserving (tweakable) encryption scheme that provides (tweakable) strong pseudorandom permutation security on arbitrarily long messages. TES is traditionally built using block ciphers and the security of the mode depends on the strong pseudorandom permutation security of the underlying block cipher. In this paper, we construct TESs using public random permutations. Public random permutations are being considered as a replacement of block cipher in several cryptographic schemes including AEs, MACs, etc. However, to our knowledge, a systematic study of constructing TES using public random permutations is missing. In this paper, we give a generic construction of a TES which uses a public random permutation, a length expanding public permutation based PRF and a hash function which is both almost xor universal and almost regular. Further, we propose a concrete length expanding public permutation based PRF construction. We also propose a single keyed TES using a public random permutation and an AXU and almost regular hash function.

In this paper, we are concerned about bounds and constructions of optimal \begin{document}$ 2 $\end{document} -D \begin{document}$ (n\times m,3,2,1) $\end{document} -optical orthogonal codes. The exact number of codewords of an optimal \begin{document}$ 2 $\end{document} -D \begin{document}$ (n\times m,3,2,1) $\end{document} -optical orthogonal code is determined for \begin{document}$ n = 2 $\end{document} , \begin{document}$ m\equiv 1 \pmod{2} $\end{document} , and \begin{document}$ n\equiv 1 \pmod{2} $\end{document} , \begin{document}$ m\equiv 1,3,5 \pmod{12} $\end{document} , and \begin{document}$ n\equiv 4 \pmod{6} $\end{document} , \begin{document}$ m\equiv 8 \pmod{16} $\end{document} .

Absorbing sets are combinatorial structures in the Tanner graphs of low-density parity-check (LDPC) codes that have been shown to inhibit the high signal-to-noise ratio performance of iterative decoders over many communication channels. Absorbing sets of minimum size are the most likely to cause errors, and thus have been the focus of much research. In this paper, we determine the sizes of absorbing sets that can occur in general and left-regular LDPC code graphs, with emphasis on the range of \begin{document}$ b $\end{document} for a given \begin{document}$ a $\end{document} for which an \begin{document}$ (a,b) $\end{document} -absorbing set may exist. We identify certain cases of extremal absorbing sets that are elementary, a particularly harmful class of absorbing sets, and also introduce the notion of minimal absorbing sets which will help in designing absorbing set removal algorithms.

We propose a decentralized e-voting protocol that is coercion-resistant and vote-selling resistant, while being also completely transparent and not receipt-free. We achieve decentralization using blockchain technology. Because of the properties such as transparency, decentralization, and non-repudiation, blockchain is a fundamental technology of great interest in its own right, and it also has large potential when integrated into many other areas. We prove the security of the protocol under the standard DDH assumption on the underlying prime-order cyclic group (e.g. the group of points of an elliptic curve), as well as under standard assumptions on blockchain robustness.

In this paper, for each of six families of three-valued \begin{document}$ m $\end{document} -sequence correlation, we construct an infinite family of five-weight codes from trace codes over the ring \begin{document}$ R = \mathbb{F}_2+u\mathbb{F}_2 $\end{document} , where \begin{document}$ u^2 = 0. $\end{document} The trace codes have the algebraic structure of abelian codes. Their Lee weight distribution is computed by using character sums. Their support structure is determined. An application to secret sharing schemes is given. The parameters of the binary image are \begin{document}$ [2^{m+1}(2^m-1),4m,2^{m}(2^m-2^r)] $\end{document} for some explicit \begin{document}$ r. $\end{document}

In this paper, we study the \begin{document}$ m $\end{document} -ary sequences with (non-consecutive) two zero-symbols and at most two distinct autocorrelation coefficients, which are known as almost \begin{document}$ m $\end{document} -ary nearly perfect sequences. We show that these sequences are equivalent to \begin{document}$ \ell $\end{document} -partial direct product difference sets (PDPDS), then we extend known results on the sequences with two consecutive zero-symbols to non-consecutive case. Next, we study the notion of multipliers and orbit combination for \begin{document}$ \ell $\end{document} -PDPDS. Finally, we present two construction methods for a family of almost quaternary sequences with at most two out-of-phase autocorrelation coefficients.

A Boolean function in \begin{document}$ n $\end{document} variables is 2-rotation symmetric if it is invariant under even powers of \begin{document}$ \rho(x_1, \ldots, x_n) = (x_2, \ldots, x_n, x_1) $\end{document} , but not under the first power (ordinary rotation symmetry); we call such a function a 2-function. A 2-function is called monomial rotation symmetric (MRS) if it is generated by applying powers of \begin{document}$ \rho^2 $\end{document} to a single monomial. If the quartic MRS 2-function in \begin{document}$ 2n $\end{document} variables has a monomial \begin{document}$ x_1 x_q x_r x_s $\end{document} , then we use the notation \begin{document}$ {2-}(1,q,r,s)_{2n} $\end{document} for the function. A detailed theory of equivalence of quartic MRS 2-functions in \begin{document}$ 2n $\end{document} variables was given in a \begin{document}$ 2020 $\end{document} paper by Cusick, Cheon and Dougan. This theory divides naturally into two classes, called \begin{document}$ mf1 $\end{document} and \begin{document}$ mf2 $\end{document} in the paper. After describing the equivalence classes, the second major problem is giving details of the linear recursions that the Hamming weights for any sequence of functions \begin{document}$ {2-}(1,q,r,s)_{2n} $\end{document} (with \begin{document}$ q say), \begin{document}$ n = s, s+1, \ldots $\end{document} can be shown to satisfy. This problem was solved for the \begin{document}$ mf1 $\end{document} case only in the \begin{document}$ 2020 $\end{document} paper. Using new ideas about "short" functions, Cusick and Cheon found formulas for the \begin{document}$ mf2 $\end{document} weights in a \begin{document}$ 2021 $\end{document} sequel to the \begin{document}$ 2020 $\end{document} paper. In this paper the actual recursions for the weights in the \begin{document}$ mf2 $\end{document} case are determined.

Let \begin{document}$ p $\end{document} be a prime and let \begin{document}$ n $\end{document} be an integer with \begin{document}$ (n, p) = 1 $\end{document} . The Fermat quotient \begin{document}$ q_p(n) $\end{document} is defined as \begin{document}$ q_p(n)\equiv \frac{n^{p-1}-1}{p} \ (\bmod\ p), \quad 0\leq q_p(n)\leq p-1. $\end{document} We also define \begin{document}$ q_p(kp) = 0 $\end{document} for \begin{document}$ k\in \mathbb{Z} $\end{document} . Chen, Ostafe and Winterhof constructed the binary sequence \begin{document}$ E_{p^2} = \left(e_0, e_1, \cdots, e_{p^2-1}\right)\in \{0, 1\}^{p^2} $\end{document} as \begin{document}$ \begin{equation*} \begin{split} e_{n} = \left\{\begin{array}{ll} 0, & \hbox{if }\ 0\leq \frac{q_p(n)}{p} and studied the well-distribution measure and correlation measure of order \begin{document}$ 2 $\end{document} by using estimates for exponential sums of Fermat quotients. In this paper we further study the correlation measures of the sequence. Our results show that the correlation measure of order \begin{document}$ 3 $\end{document} is quite good, but the \begin{document}$ 4 $\end{document} -order correlation measure of the sequence is very large.

Key assignment and key maintenance in encrypted networks of resource-limited devices may be a challenging task, due to the permanent need of replacing out-of-service devices with new ones and to the consequent need of updating the key information. Recently, Aragona et al. proposed a new cryptographic scheme, ECTAKS, which provides a solution to this design problem by means of a Diffie-Hellman-like key establishment protocol based on elliptic curves and on a prime field. Even if the authors proved some results related to the security of the scheme, the latter still lacks a formal security analysis. In this paper, we address this issue by providing a security proof for ECTAKS in the setting of computational security, assuming that no adversary can solve the underlying discrete logarithm problems with non-negligible success probability.

In this paper, we propose cryptanalytic results on two lightweight stream ciphers: Fountain v1 and Lizard. The main results of this paper are the followings: \begin{document}$ - $\end{document} We propose a zero-sum distinguisher on reduced round Fountain v1. In this context, we study the non-randomness of the cipher with a careful selection of cube variables. Our obtained cube provides a zero-sum on Fountain v1 till \begin{document}$ 188 $\end{document} initialization rounds and significant non-randomness till \begin{document}$ 189 $\end{document} rounds. This results in a distinguishing attack on Fountain v1 with \begin{document}$ 189 $\end{document} initialization rounds. \begin{document}$ - $\end{document} Further, we find that the same cipher has a weakness against conditional Time-Memory-Data-Tradeoff (TMDTO). We show that TMDTO attack using sampling resistance has online complexity \begin{document}$ 2^{110} $\end{document} and offline complexity \begin{document}$ 2^{146} $\end{document} . \begin{document}$ - $\end{document} Finally, we revisit the Time-Memory-Data-Tradeoff attack on Lizard by Maitra et al. (IEEE Transactions on Computers, 2018) and provide our observations on their work. We show that instead of choosing any random string, some particular strings would provide better results in their proposed attack technique.

A generalized Stirling numbers of the second kind \begin{document}$ S_{a,b}\left(p,k\right) $\end{document} , involved in the expansion \begin{document}$ \left(an+b\right)^{p} = \sum_{k = 0}^{p}k!S_{a,b}\left(p,k\right) \binom{n}{k} $\end{document} , where \begin{document}$ a \neq 0, b $\end{document} are complex numbers, have studied in [ 16 ]. In this paper, we show that Bernoulli polynomials \begin{document}$ B_{p}(x) $\end{document} can be written in terms of the numbers \begin{document}$ S_{1,x}\left(p,k\right) $\end{document} , and then use the known results for \begin{document}$ S_{1,x}\left(p,k\right) $\end{document} to obtain several new explicit formulas, recurrences and generalized recurrences for Bernoulli numbers and polynomials.

In the context of digital signatures, the proxy signature holds a significant role of enabling an original signer to delegate its signing ability to another party (i.e., proxy signer). It has significant practical applications. Particularly it is useful in distributed systems, where delegation of authentication rights is quite common. For example, key sharing protocol, grid computing, and mobile communications. Currently, a large portion of existing proxy signature schemes are based on the hardness of problems like integer factoring, discrete logarithms, and/or elliptic curve discrete logarithms. However, with the rising of quantum computers, the problem of prime factorization and discrete logarithm will be solvable in polynomial-time, due to Shor's algorithm, which dilutes the security features of existing ElGamal, RSA, ECC, and the proxy signature schemes based on these problems. As a consequence, construction of secure and efficient post-quantum proxy signature becomes necessary. In this work, we develop a post-quantum proxy signature scheme Mult-proxy, relying on multivariate public key cryptography (MPKC), which is one of the most promising candidates of post-quantum cryptography. We employ a 5-pass identification protocol to design our proxy signature scheme. Our work attains the usual proxy criterion and a one-more-unforgeability criterion under the hardness of the Multivariate Quadratic polynomial (MQ) problem. It produces optimal size proxy signatures and optimal size proxy shares in the field of MPKC.

Regev (2005) introduced the learning with errors (LWE) problem and showed a quantum reduction from a worst case lattice problem to LWE. Building on the work of Peikert (2009), a classical reduction from the gap shortest vector problem to LWE was obtained by Brakerski et al. (2013). A concrete security analysis of Regev's reduction by Chatterjee et al. (2016) identified a huge tightness gap. The present work performs a concrete analysis of the tightness gap in the classical reduction of Brakerski et al. It turns out that the tightness gap in the Brakerski et al. classical reduction is even larger than the tightness gap in the quantum reduction of Regev. This casts doubts on the implication of the reduction to security assurance of practical cryptosystems.

The number of proper vertex-3-colorings of every triangle-free planar graph with n vertices and with no separating cycle of length 4 or 5 is at least 2 n / 17700000 . On the other hand, for infinitely many n, there exists a triangle-free planar graph with separating cycles of length 4 and 5 whose number of proper vertex-3-colorings is 2 15 n / log 2 ⁡ ( n ) .

In this paper, we first introduce a class of quartic Boolean functions. And then, the construction of weightwise perfectly balanced Boolean functions on \begin{document}$ 2^m $\end{document} variables are given by modifying the support of the quartic functions, where \begin{document}$ m $\end{document} is a positive integer. The algebraic degree, the weightwise nonlinearity, and the algebraic immunity of the newly constructed weightwise perfectly balanced functions are discussed at the end of this paper.

We prove that pseudorandom sets in the Grassmann graph have near-perfect expansion. This completes the last missing piece of the proof of the 2-to-2-Games Conjecture (albeit with imperfect completeness). The Grassmann graph has induced subgraphs that are themselves isomorphic to Grassmann graphs of lower orders. A set of vertices is called pseudorandom if its density within all such subgraphs (of constant order) is at most slightly higher than its density in the entire graph. We prove that pseudorandom sets have almost no edges within them. Namely, their edge-expansion is very close to 1.

Given a set $P$ of $n$ points in $\mathbb{R}^2$ and an input line $\gamma$ in $\mathbb{R}^2$, we present an algorithm that runs in optimal $\Theta(n\log n)$ time and $\Theta(n)$ space to solve a restricted version of the $1$-Steiner tree problem. Our algorithm returns a minimum-weight tree interconnecting $P$ using at most one Steiner point $s \in \gamma$, where edges are weighted by the Euclidean distance between their endpoints. We then extend the result to $j$ input lines. Following this, we show how the algorithm of Brazil et al. ("Generalised k-Steiner Tree Problems in Normed Planes", arXiv:1111.1464) that solves the $k$-Steiner tree problem in $\mathbb{R}^2$ in $O(n^{2k})$ time can be adapted to our setting. For $k>1$, restricting the (at most) $k$ Steiner points to lie on an input line, the runtime becomes $O(n^{k})$. Next we show how the results of Brazil et al. ("Generalised k-Steiner Tree Problems in Normed Planes", arXiv:1111.1464) allow us to maintain the same time and space bounds while extending to some non-Euclidean norms and different tree cost functions. Lastly, we extend the result to $j$ input curves., Comment: 31 pages (26 of content), 4 figures (last one as 3 subfigures). Minor corrections since publication: notably our analysis of the Brazil et al. k-steiner tree algorithm in section 4.1 (results unchanged), and a correction to some corollary statements to correct the space usage. Also added short discussion of how the algorithm still works when the MST of the input point set is not unique

Graph sparsification underlies a large number of algorithms, ranging from approximation algorithms for cut problems to solvers for linear systems in the graph Laplacian. In its strongest form, "spectral sparsification" reduces the number of edges to near-linear in the number of nodes, while approximately preserving the cut and spectral structure of the graph. In this work we demonstrate a polynomial quantum speedup for spectral sparsification and many of its applications. In particular, we give a quantum algorithm that, given a weighted graph with $n$ nodes and $m$ edges, outputs a classical description of an $\epsilon$-spectral sparsifier in sublinear time $\tilde{O}(\sqrt{mn}/\epsilon)$. This contrasts with the optimal classical complexity $\tilde{O}(m)$. We also prove that our quantum algorithm is optimal up to polylog-factors. The algorithm builds on a string of existing results on sparsification, graph spanners, quantum algorithms for shortest paths, and efficient constructions for $k$-wise independent random strings. Our algorithm implies a quantum speedup for solving Laplacian systems and for approximating a range of cut problems such as min cut and sparsest cut., Comment: v2: several small improvements to the text. An extended abstract will appear in FOCS'20; v3: corrected a minor mistake in Appendix A; v4: final version as published in SICOMP

We prove the following theorem. Given a planar graph $G$ and an integer $k$, it is possible in polynomial time to randomly sample a subset $A$ of vertices of $G$ with the following properties: (i) $A$ induces a subgraph of $G$ of treewidth $\mathcal{O}(\sqrt{k}\log k)$, and (ii) for every connected subgraph $H$ of $G$ on at most $k$ vertices, the probability that $A$ covers the whole vertex set of $H$ is at least $(2^{\mathcal{O}(\sqrt{k}\log^2 k)}\cdot n^{\mathcal{O}(1)})^{-1}$, where $n$ is the number of vertices of $G$. Together with standard dynamic programming techniques for graphs of bounded treewidth, this result gives a versatile technique for obtaining (randomized) subexponential parameterized algorithms for problems on planar graphs, usually with running time bound $2^{\mathcal{O}(\sqrt{k} \log^2 k)} n^{\mathcal{O}(1)}$. The technique can be applied to problems expressible as searching for a small, connected pattern with a prescribed property in a large host graph, examples of such problems include Directed $k$-Path, Weighted $k$-Path, Vertex Cover Local Search, and Subgraph Isomorphism, among others. Up to this point, it was open whether these problems can be solved in subexponential parameterized time on planar graphs, because they are not amenable to the classic technique of bidimensionality. Furthermore, all our results hold in fact on any class of graphs that exclude a fixed apex graph as a minor, in particular on graphs embeddable in any fixed surface.

What does it mean today to study a problem from a computational point of view? We focus on parameterized complexity and on Column 16 “Graph Restrictions and Their Effect” of D.S. Johnson’s Ongoing guide, where several puzzles were proposed in a summary table with 30 graph classes as rows and 11 problems as columns. Several of the 330 entries remain unclassified into Polynomial or NP -complete after 35 years. We provide a full dichotomy for the Steiner Tree column by proving that the problem is NP -complete when restricted to Undirected Path graphs. We revise Johnson’s summary table according to the granularity provided by the parameterized complexity for NP -complete problems.

Rainbow coloring problems, of noteworthy applications in Information Security, have been receiving much attention in the last years in Combinatorics. In particular, the rainbow connection number of a connected graph G , denoted r c ( G ) , is the least k for which G admits a (not necessarily proper) k -edge-coloring such that between any pair of vertices there is a path whose edge colors are all distinct. When G is disconnected, we define r c ( G ) = ∞ . A graph G is rainbow critical if the deletion of any edge of G increases r c ( G ) . In this paper we determine the rainbow connection number for the shadow graphs of paths, some circulant graphs, and some Cartesian products involving cycles and paths. We also determine conditions for the rainbow criticality and non-criticality of wheels, fans, and some Cartesian products involving cycles, paths, pans, and complete graphs.

Let G be a connected graph of order n , A ( G ) the adjacency matrix of G and D ( G ) the diagonal matrix of the row-sums of A ( G ) . For every real α ∈ [ 0 , 1 ] , Nikiforov defined the matrix A α ( G ) as A α ( G ) = α D ( G ) + ( 1 − α ) A ( G ) . In this paper, we obtain a factorization of the A α -characteristic polynomial of the some families of graphs and determine in these families the conditions about α so that A α ( G ) is positive semidefinite.

In this paper, we initiate the study of the weighted paging problem with predictions. This continues the recent line of work in online algorithms with predictions, particularly that of Lykouris and Vassilvitski (ICML 2018) and Rohatgi (SODA 2020) on unweighted paging with predictions. We show that unlike unweighted paging, neither a fixed lookahead nor knowledge of the next request for every page is sufficient information for an algorithm to overcome existing lower bounds in weighted paging. However, a combination of the two, which we call the strong per request prediction (SPRP) model, suffices to give a 2-competitive algorithm. We also explore the question of gracefully degrading algorithms with increasing prediction error, and give both upper and lower bounds for a set of natural measures of prediction error., Comment: 27 pages

We present a generalization of a combinatorial result by Aggarwal et al. (1989) on a linear-time algorithm that selects a constant fraction of leaves, with pairwise disjoint neighborhoods, from a binary tree embedded in the plane. This result of Aggarwal et al. (1989) is essential to the linear-time framework, which they also introduced, that computes certain Voronoi diagrams of points with a tree structure in linear time. An example is the diagram computed while updating the Voronoi diagram of points after deletion of one site. Our generalization allows that only a fraction of the tree leaves is considered, and it is motivated by research on linear time construction algorithms for Voronoi diagrams of non-point sites. We are given a plane tree T of n leaves, m of which have been marked, and each marked leaf is associated with a neighborhood (a subtree of T ) such that any two topologically consecutive marked leaves have disjoint neighborhoods. We show how to select in linear time a constant fraction of the marked leaves having pairwise disjoint neighborhoods.

The main objective of this article is to study the Wiener index of zero-divisor graph of the ring of integer modulo n . We present a constructed method to calculate the Wiener index of zero-divisor graph of Z n for any positive integer n .

We characterize the optimal solution to the linear programming relaxation of the standard formulation for the minimum satisfiability problem. We give a O ( n m 2 ) combinatorial algorithm to solve the fractional version of the minimum satisfiability problem optimally where n ( m ) is the number of variables (clauses). As a by-product, we obtain a 2 ( 1 − 1 ∕ 2 k ) approximation algorithm for the minimum satisfiability problem where k is the maximum number of literals in any clause.

The eternal vertex cover problem is a variant of the classical vertex cover problem defined in terms of an infinite attacker–defender game played on a graph. In each round of the game, the defender reconfigures guards from one vertex cover to another in response to a move by the attacker. The minimum number of guards required in any winning strategy of the defender when this game is played on a graph G is the eternal vertex cover number of G , denoted by evc ( G ) . It is known that given a graph G and an integer k , checking whether evc ( G ) ≤ k is NP-hard. Further, it is known that for any graph G , mvc ( G ) ≤ evc ( G ) ≤ 2 mvc ( G ) , where mvc ( G ) is the vertex cover number of G . Though a characterization is known for graphs for which evc ( G ) = 2 mvc ( G ) , a characterization of graphs for which evc ( G ) = mvc ( G ) remained as an open problem, since 2009. We achieve such a characterization for a class of graphs that includes chordal graphs and internally triangulated planar graphs. For biconnected chordal graphs, our characterization leads to a polynomial time algorithm for precisely determining evc ( G ) and an algorithm for determining a safe strategy for guard movement in each round of the game using only evc ( G ) guards. Though the eternal vertex cover problem is only known to be in PSPACE in general, it follows from our new characterization that the problem is in NP for locally connected graphs, a graph class which includes all biconnected internally triangulated planar graphs. We also provide reductions establishing NP-completeness of the problem for biconnected internally triangulated planar graphs. As far as we know, this is the first NP-completeness result known for the problem for any graph class.

In this paper, we study the Cartesian product of signed graphs as defined by Germina, Hameed and Zaslavsky (2011). Here we focus on its algebraic properties and look at the chromatic number of some Cartesian products. One of our main results is the unicity of the prime factor decomposition of signed graphs. This leads us to present an algorithm to compute this decomposition in linear time based on a decomposition algorithm for oriented graphs by Imrich and Peterin (2018). We also study the chromatic number of a signed graph, that is the minimum order of a signed graph to which the input signed graph admits a homomorphism, of graphs with underlying graph of the form P n □ P m , of Cartesian products of signed paths, of Cartesian products of signed complete graphs and of Cartesian products of signed cycles.

In communication networks, the existence of fractional factors can be characterized as the feasibility of data transmission. When some nonadjacent nodes with each other are damaged and a special channel is assigned, the possibility of data transmission in a communication network is equivalent to the existence of fractional ID-factor-critical covered graph. As a consequence, the existence of fractional ID- [ a , b ] -factor-critical covered graph plays a key role in studying data transmissions of communication networks. Neighborhood and minimum degree of a graph or a network are often used to measure the vulnerability and robustness of a graph or a network, which are two important parameters considered in network design. In this article, we mainly investigate the relationship between neighborhood of independent set, minimum degree and the fractional ID- [ a , b ] -factor-critical covered graph, and acquire a neighborhood of independent set and minimum degree condition for a graph being fractional ID- [ a , b ] -factor-critical covered, which is a generalization of the previous results.

Indicated coloring is a graph coloring game in which two players collectively color the vertices of a graph in the following way. In each round the first player (Ann) selects a vertex, and then the second player (Ben) colors it properly, using a fixed set of colors. The goal of Ann is to achieve a proper coloring of the whole graph, while Ben is trying to prevent the realization of this project. The smallest number of colors necessary for Ann to win the game on a graph $G$ (regardless of Ben's strategy) is called the indicated chromatic number of $G$, denoted by $\chi_i(G)$. In this paper, we have shown that for any graphs $G$ and $H$, $G[H]$ is $k$-indicated colorable for all $k\geq\mathrm{col}(G)\mathrm{col}(H)$. Also, we have shown that for any graph $G$ and for some classes of graphs $H$ with $\chi(H)=\chi_i(H)=\ell$, $G[H]$ is $k$-indicated colorable if and only if $G[K_\ell]$ is $k$-indicated colorable. As a consequence of this result we have shown that for some particular families of graphs $G$ and $H$, $G[H]$ is $k$-indicated colorable for every $k\geq \chi(G[H])$. This serves as a partial answer to one of the questions raised by A. Grzesik in \cite{and}. In addition, if $G$ is a Bipartite graph or a $\{P_5,K_3\}$-free graph (or) a $\{P_5,Paw\}$-free graph and if $H$ is from the same families of graphs, then we have shown that $\chi_i(G[H])=\chi(G[H])$.

A subset D ⊆ V of a graph G = ( V , E ) is called a global total k -dominating set of G if D is a total k -dominating set of both G and G ¯ , the complement of G . The Minimum Global Total k - Domination problem is to find a global total k -dominating set of minimum cardinality of the input graph G and the Decide Global Total k - Domination problem is the decision version of the Minimum Global Total k - Domination problem. The Decide Global Total k - Domination problem is known to be NP -complete for general graphs. In this paper, we study the complexity of the Minimum Global Total k - Domination problem. We show the Decide Global Total k - Domination problem remains NP -complete for bipartite graphs and chordal graphs. We also show that Minimum Global Total k - Domination cannot be approximated within a factor of ( 1 − ϵ ) ln | V | for any ϵ > 0 unless P = NP for bipartite graphs as well as for chordal graphs. Next, we show that Minimum Global Total k - Domination admits a constant approximation algorithm for bounded degree graphs. Finally, we show that Minimum Global Total k - Domination problem is APX -complete for bounded degree graphs. We also show that Decide Global Total k - Domination problem is W[2] -hard for bipartite graphs and for chordal graphs when we choose the size of the GTkD-set as the parameter.

In an undirected graph, a matching cut is a partition of vertices into two sets such that the edges across the sets induce a matching. The Matching Cut problem is the problem of deciding whether a given graph has a matching cut. Let H be a fixed undirected graph. A vertex coloring of an undirected input graph G is said to be an H - Free Coloring if none of the color classes contain H as an induced subgraph. The H - Free Chromatic Number of G is the minimum number of colors required for an H - Free Coloring of G . Both The Matching Cut problem and the H - Free Coloring problem can be expressed using a monadic second-order logic (MSOL) formula and hence is solvable in linear time for graphs with bounded tree-width. However, this approach leads to a running time of f ( | | φ | | , t ) n O ( 1 ) , where | | φ | | is the length of the MSOL formula, t is the tree-width of the graph and n is the number of vertices of the graph. The dependency of f ( | | φ | | , t ) on | | φ | | can be as bad as a tower of exponentials. In this paper, we provide explicit combinatorial FPT algorithms for Matching Cut problem and H - Free Coloring problem, parameterized by the tree-width of G . The single exponential FPT algorithm for the Matching Cut problem answers an open question posed by Kratsch and Le (2016). The techniques used in the paper are also used to provide an FPT algorithm for a variant of H -free coloring, where H is forbidden as a subgraph (not necessarily induced) in the color classes of G .

Sierpinski triangle graphs S n have often been mistaken for Sierpinski graphs S 3 n . Whereas the latter’s metric properties are by now well understood, the former graphs were mostly just considered as a pictorial representation of approximations to the Sierpinski triangle fractal. Therefore, we present here a new labeling for them which shows the relation, but also the differences to the more famous Sierpinski graphs proper. On the base of this labeling we describe an algorithm to obtain individual distances between vertices. This type of algorithm can then be extended to base- p Sierpinski triangle graphs S p n which are related to the class of classical Sierpinski graphs S p n , p ≥ 2 . Some of the metric properties of S p n can now be investigated for S p n as well; e.g., we characterize center and periphery of S p n .

Consider a variant of the famous Tower of Hanoi problem where moves of the discs are allowed along the edges of a connected simple graph D whose vertices represent the vertical pegs of the puzzle. The task is to transfer a tower of n ∈ N discs from one peg to another according to the well-known rules of the classical game corresponding to D ≅ K 3 . Apart from its recreational appeal, the problem brings about fascinating integer sequences engendered by the respective minimum number of moves, i.e. the distance in the canonical metric of the state graph H D n . We construct an algorithm which solves the task for all cases but the exceptional instance of the Linear Tower of Hanoi (i.e. where D is a path graph) in which the transfer is between the two end vertices of D . Optimality of this algorithm is claimed in our central conjecture which is supported by large-scale computational explorations.

An {\em orientation} of an undirected graph $G$ is an assignment of exactly one direction to each edge of $G$. Converting two-way traffic networks to one-way traffic networks and bidirectional communication networks to unidirectional communication networks are practical instances of graph orientations. In these contexts minimising the diameter of the resulting oriented graph is of prime interest. The $n$-star network topology was proposed as an alternative to the hypercube network topology for multiprocessor systems by Akers and Krishnamurthy [IEEE Trans. on Computers (1989)]. The $n$-star graph $S_n$ consists of $n!$ vertices, each labelled with a distinct permutation of $[n]$. Two vertices are adjacent if their labels differ exactly in the first and one other position. $S_n$ is an $(n-1)$-regular, vertex-transitive graph with diameter $\lfloor 3(n-1)/2 \rfloor$. Orientations of $S_n$, called unidirectional star graphs and distributed routing protocols over them were studied by Day and Tripathi [Information Processing Letters (1993)] and Fujita [The First International Symposium on Computing and Networking (CANDAR 2013)]. Fujita showed that the (directed) diameter of this unidirectional star graph $\overrightarrow{S_n}$ is at most $\lceil{5n/2}\rceil + 2$. In this paper, we propose a new distributed routing algorithm for the same $\overrightarrow{S_n}$ analysed by Fujita, which routes a packet from any node $s$ to any node $t$ at an undirected distance $d$ from $s$ using at most $\min\{4d+4, 2n+4\}$ hops. This shows that the (directed) diameter of $\overrightarrow{S_n}$ is at most $2n+4$. We also show that the diameter of $\overrightarrow{S_n}$ is at least $2n$ when $n \geq 7$, thereby showing that our upper bound is tight up to an additive factor., Full version of the paper to be presented in CALDAM 2020

A graph G is P ≥ k -factor deleted if for every edge e ∈ E ( G ) , G contains a P ≥ k -factor that excludes e . We first define the concept of ( P ≥ k , n ) -critical deleted graph, that is, a graph G is ( P ≥ k , n ) -critical deleted if for every subset D ⊆ V ( G ) with | D | = n , the graph G − D is P ≥ k -factor deleted. Clearly, a ( P ≥ k , 0 ) -critical deleted graph is a P ≥ k -factor deleted graph. In this paper, we verify that (i) an ( n + 2 ) -connected graph G is ( P ≥ 2 , n ) -critical deleted if its binding number b i n d ( G ) > 3 + n 4 ; (ii) an ( n + 2 ) -connected graph G is ( P ≥ 3 , n ) -critical deleted if its binding number b i n d ( G ) > 3 + n 2 . Furthermore, we claim that two results above are best possible in some sense.

Given a graph G , we call a partition ( V 1 , V 2 , … , V k ) of its vertex set an induced star partition of G if each set in the partition induces a star. In this paper, we consider the problem of finding an induced star partition of a graph of minimum size and its decision versions. This problem may be viewed as an amalgamation of the well-known dominating set and coloring problems. We obtain the following main results: (1) Deciding whether a graph can be partitioned into k induced stars is NP-complete for each fixed k ≥ 3 and has a polynomial time algorithm for each k ≤ 2 . (2) It is NP-hard to approximate the minimum induced star partition size within n 1 2 − ϵ for all ϵ > 0 . (3) The decision version of the induced star partition problem is NP-complete for subcubic bipartite planar graphs, line graphs (a subclass of K 1 , r -free graphs, r ≥ 3 ), K 1 , 5 -free split graphs and co-tripartite graphs. (4) The minimum induced star partition problem has an r 2 -approximation algorithm for K 1 , r -free graphs ( r ≥ 2 ) and a 2-approximation algorithms for split graphs. We also identify some fixed parameter tractable and exact exponential time algorithms that follow from the literature.

Let G = ( V , E ) be a simple undirected graph. A set D ⊆ V is called a vertex-edge dominating set of G if for each edge e = u v ∈ E , either u or v is in D or one vertex from their neighbor is in D . Simply, a vertex v ∈ V , vertex-edge dominates every edge u v , as well as every edge adjacent to these edges. The objective of the vertex-edge domination problem is to find a minimum size vertex-edge dominating set of G . Herein, we study the vertex-edge domination problem in unit disk graphs and prove that the decision version of the problem belongs to the NP-complete class. We also show that the problem admits a simple polynomial-time 4-factor approximation algorithm and a polynomial-time approximation scheme (PTAS) in unit disk graphs.

For a given graph $G$, the metric and edge metric dimensions of $G$, $\dim(G)$ and ${\rm edim}(G)$, are the cardinalities of the smallest possible subsets of vertices in $V(G)$ such that they uniquely identify the vertices and the edges of $G$, respectively, by means of distances. It is already known that metric and edge metric dimensions are not in general comparable. Infinite families of graphs with pendant vertices in which the edge metric dimension is smaller than the metric dimension are already known. In this article, we construct a 2-connected graph $G$ such that $\dim(G)=a$ and ${\rm edim}(G)=b$ for every pair of integers $a,b$, where $4\le b, Comment: 12 pages